function [ sensors ] = gaps_alg( dataset, k, m, c )
%random_alg GAPS algorith described in section 4, alg 3
%   Greedily picks placement and schedule, optimizes for average fitness.
%   Picks m sensors from the dataset and distributes across k times.

    % This matrix stores all possible times, and what sensors are in them
    % Zeros represent empty slots. Since this is matlab, the matrix is big
    ats = zeros(k, m);
    % Index of first zero in each time slot in the above matrix
    ats_zero = ones(k, 1);
    
    % List of sensors that haven't been added to any time
    unsched = 1;
    for i=2:size(dataset,2)
        unsched = union(unsched, i);
    end

    % Loop, adding one sensor each time
    for i=1:m

        % This matrix stores the deltas for this loop iteration
        deltas = zeros(k, size(unsched, 2));

        % Loop over all unscheduled sensors and times
        for s=1:size(unsched, 2)
            for t=1:k
                % Fill in the delta table
                cost_s = get_quality(dataset, union(ats(t,:), unsched(s)), c);
                cost = get_quality(dataset, ats(t,:), c);
                deltas(t, s) = cost_s - cost;
            end
        end
        
        % Find the best delta for each time
        [dontcare, bestpos] = max(deltas, [], 2);
        
        % Loop over the best for each time, and find the overall best
        bests = bestpos(1);
        bestt = 1;
        curbest = deltas(1, bests);
        for t = 2:k
            if(deltas(t, bestpos(t)) > curbest)
                bests = bestpos(t);
                bestt = t;
                curbest = deltas(t, bestpos(t));
            end
        end
        % Add that element to At
        ats(bestt, ats_zero(bestt)) = unsched(bests);
        ats_zero(bestt) = ats_zero(bestt) + 1;
        
        % Remove it from unsched
        unsched = setdiff(unsched, unsched(bests));
    end
    
    % Build the list of sensors from ats
    sensors = zeros(2, m);
    nextsensor = 1;
    % Loop over each row of ats
    for t = 1:k
        for i = 1:(ats_zero(t) - 1)
            sensors(1, nextsensor) = ats(t, i);
            sensors(2, nextsensor) = t;
            nextsensor = nextsensor + 1;
        end
    end

end
